Wildcard Matching

LeetCode 44 | Difficulty: Hard

Hard

Problem Description

Given an input string (s) and a pattern (p), implement wildcard pattern matching with support for '?' and '*' where:

- `'?'` Matches any single character.

- `'*'` Matches any sequence of characters (including the empty sequence).

The matching should cover the entire input string (not partial).

Example 1:

Input: s = "aa", p = "a"
Output: false
Explanation: "a" does not match the entire string "aa".

Example 2:

Input: s = "aa", p = "*"
Output: true
Explanation: '*' matches any sequence.

Example 3:

Input: s = "cb", p = "?a"
Output: false
Explanation: '?' matches 'c', but the second letter is 'a', which does not match 'b'.

Constraints:

- `0 <= s.length, p.length <= 2000`

- `s` contains only lowercase English letters.

- `p` contains only lowercase English letters, `'?'` or `'*'`.

Topics: String, Dynamic Programming, Greedy, Recursion

---

Approach

Dynamic Programming

Break the problem into overlapping subproblems. Define a state (what information do you need?), a recurrence (how does state[i] depend on smaller states?), and a base case. Consider both top-down (memoization) and bottom-up (tabulation) approaches.

When to use

Optimal substructure + overlapping subproblems (counting ways, min/max cost, feasibility).

Greedy

At each step, make the locally optimal choice. The challenge is proving the greedy choice leads to a global optimum. Look for: can I sort by some criterion? Does choosing the best option now ever hurt future choices?

When to use

Interval scheduling, activity selection, minimum coins (certain denominations), Huffman coding.

String Processing

Consider character frequency counts, two-pointer approaches, or building strings efficiently. For pattern matching, think about KMP or rolling hash. For palindromes, expand from center or use DP.

When to use

Anagram detection, palindrome checking, string transformation, pattern matching.

---

Solutions

Solution 1: C# (Best: 148 ms)

Metric	Value
Runtime	148 ms
Memory	N/A
Date	2018-03-01

Solution

public class Solution {
    public bool IsMatch(string s, string p) {
    int m=s.Length, n=p.Length;
    char[] sc = s.ToCharArray();
    char[] pc = p.ToCharArray();
    bool[,] dp = new bool[m+1,n+1];
    dp[0,0]= true;
        //dp.Dump();
    for (int j = 1; j < n+1; j++)
    {
        if(pc[j-1]=='*') {
            dp[0,j] = dp[0,j-1];
        }
    }   

    for (int i = 1; i < m+1; i++)
    {
        for (int j = 1; j < n+1; j++)
        {
            if(pc[j-1]==sc[i-1] || pc[j-1] == '?')
            {
                dp[i,j] = dp[i-1,j-1];
            }
            else if(pc[j-1] == '*')
            {
                dp[i,j] = dp[i-1,j] || dp[i,j-1];
            }
            else {
                dp[i,j] = false;
            }
            //dp.Dump();
        }
    }
    
    return dp[m,n];
    }
}

📜 1 more C# submission(s)

Submission (2018-02-28) — 224 ms, N/A

public class Solution {
    public bool IsMatch(string s, string p) {
    int si = 0, pi = 0, star = -1, match = 0;
    while (si < s.Length)
    {
        if (pi < p.Length && (s[si] == p[pi] || p[pi] == '?'))
        {
            si++; pi++;
        }
        else if(pi < p.Length && p[pi]=='*')
        {
            star=pi;
            match = si;
            pi++;
        }
        else if(star != -1)
        {
            pi = star+1;
            si = ++match;
        }
        
        else return false;
        Console.WriteLine($"{si} {pi} {star} {match}");
    }
    while(pi<p.Length && p[pi] == '*')
    {
        pi++;
    }
    
    return pi==p.Length;
    }
}

---

Complexity Analysis

Approach	Time	Space
DP (2D)	$O(n × m)$	$O(n × m)$

---

Interview Tips

Key Points

• Break the problem into smaller subproblems. Communicate your approach before coding.
• Define the DP state clearly. Ask: "What is the minimum information I need to make a decision at each step?"
• Consider if you can reduce space by only keeping the last row/few values.